Communication networks are being developed which operate in the asynchronous transfer mode (ATM) in which relatively short packets of data, called cells, propagate across the network from source to destination. An ATM switch, illustrated diagrammatically in FIG. 1, is located at each node of the network and includes a switch fabric 10 which must transfer a particular cell coming from any of the input channels 12 to a selected one of multiple output channels 14. In the simple illustrated switch, data contained in the cell determine which output channel 14 is selected for that cell. The input channels 12 are not synchronized with each other, but the switch achieves synchronous operation by temporarily storing cells arriving on a particular input channel 12 in an associated input buffer 16. The filled elements of the buffers 16 are marked by X's in the figure. On the other hand, an ATM switch does not have output buffers, but the cell is transmitted as soon as it routed to the correct output channel 14.
The ATM switch performs each of a set of operations in a repetitive period called the transmission cell slot. One of the cells waiting in each of the buffers 16, usually the oldest cell in the queue, is transferred to an empty corresponding transfer register 18. In the simple and conceptual illustrated switch fabric 10, transfer channels 19 (only some of which are illustrated) extend from each of the transfer register 18 to each of multiple output ports 22. Each of the transfer channels 19 has a gate 21 controlled by a scheduler 20 through gate control lines 23. In operational systems, the physical details of the transferring mechanism may be significantly different, for example, as disclosed in the later cited reference to Lee et al. The scheduler 20 examines all the cells waiting in the transfer registers 18 through query lines 25, determines from reading the cells' destinations to which output ports 22 they should be transferred, resolves any contentions when cells in two or more transfer registers 18 should be transferred to the same output port 22, and transfers as many as possible of the cells to the proper output ports 22 consistent with the contention resolution. That is, if contention exists, not all cells are transferred and the transfer registers 18 of the unselected cells remain filled into the next transmission cell slot. Any filled output port 22 has its cell transmitted onto the associated output channel 14. In the following discussion, each transfer register 18 and its associated buffer 16 will be referred to as an input port. In the simple architecture of FIG. 1, the scheduler 20 interacts with the input ports only through the transfer registers 18.
The scheduler 20 resolves the contention so that no more than one cell is transferred to a particular output port 22 in any transmission slot. Excessive contention or poor resolution of contention will result in overflow of one or more buffers 16 and the resulting loss of cells. Ideally, the scheduler 20 optimally schedules the transfers within time constraints imposed by the switch architecture while also incorporating priority and fairness. Additionally, it should schedule for a mixture of different types of transmission requests. The scheduler 20 needs to read the destination address in the input port.
Transmission requests can be divided into three types relevant to the scheduling problem: unicasts, non-atomic multicasts, and atomic multicasts. For unicasts, an input cell requests transmission to only one output port. For multicasts, an input cell requests transmission to at least two output ports. In a non-atomic multicast transmission, the switch may transfer the cell to multiple output ports in different transmission slots. In an atomic multicast transmission, the switch must transfer the cell to all the requested output ports in a single transmission slot. That is, the cell is either successfully transmitted to all requested output ports in that slot or it is not transmitted at all. Scheduling unicasts and non-atomic multicasts are special cases of scheduling atomic multicasts. A unicast is an atomic multicast to a single destination. A non-atomic multicast can be scheduled as a sequence of atomic multicasts to subsets of the set of requested output ports. Hence, a system capable of scheduling atomic multicasts will also have the ability to handle mixes of different types of requests.
Lee et al. have disclosed a multicasting scheduler in "A broadband optical multicast switch," Proceedings of the XIII International Switching Symposium, 1990, volume 3, pages 7-13. Their switch fabric involves optical wavelength-division multiplexing over a star coupler with the output ports being frequency tunable to the different input ports, but contention over output ports still requires resolution. A token is serially passed between the input ports. The token allocates for each output port an availability bit and a source address (ultimately the wavelength associated with that source). An input port examines the token. If all the output ports it needs are available, it changes the desired availability bits to indicate unavailability and writes its address into all the associated source addresses. If all the desired output ports are not available, it passes the token on unchanged. After the token has passed through all input ports, it passes to the output ports, each of which examines the source address allocated to it and which now determines the optical frequency to which it must tune for the next cell transmission cycle. Thereafter, all input ports transmit through the star coupler at their dedicated optical frequencies. Such sequential operation on both the input and output sides is considered to be too slow.